#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>

using namespace std;

class MinStack {
public:
    MinStack() {
    }

    void push(int val) {
        s.push(val);
    }

    void pop() {
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        int i = 0;
        stack<int> tmp = this->s;
        vector<int> v;
        while (!tmp.empty())
        {
            v.push_back(tmp.top());
            tmp.pop();
        }
        sort(v.begin(), v.end());
        return v[0];
    }
private:
    stack<int> s;
};


class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int push = 0;
        int pop = 0;
        int num = 0;
        vector<int> v;
        vector<int> vs;
        while (pop != popV.size())
        {
            if (popV[pop] >= pushV[push])
            {
                v.push_back(pushV[push]);
                if (push + 1 != pushV.size())
                {
                    push++;
                }
                else
                {
                    pop++;
                }
            }
            else
            {
                num = v[v.size() - 1];
                v.pop_back();
                vs.push_back(num);
                pop++;

            }
        }
        if (vs.empty())
        {
            num = v[v.size() - 1];
            vs.push_back(num);
        }
        for (int i = 0; i < popV.size(); i++)
        {
            if (vs[i] != popV[i])
            {
                return 0;
            }
        }
        return 1;
    }
};

int main()
{
    vector<int> pushV;
    vector<int> popV;

    pushV.push_back(1);
    pushV.push_back(2);
    pushV.push_back(3);
    pushV.push_back(4);
    pushV.push_back(5);

    popV.push_back(4);
    popV.push_back(5);
    popV.push_back(3);
    popV.push_back(2);
    popV.push_back(1);

    Solution s;
    cout << s.IsPopOrder(pushV, popV) << endl;
}

//int main()
//{
//    MinStack s;
//    s.push(9);
//    s.push(8);
//    s.push(7);
//    s.push(6);
//    s.push(5);
//    s.push(4);
//    s.push(3);
//    s.push(2);
//    s.push(1);
//    s.push(4);
//    s.push(9);
//    s.push(8);
//    s.push(7);
//    s.push(6);
//    cout << s.getMin() << endl;
//    return 0;
//}